/*****************************************************************
                       Ok V8 - instantiate CBmaps
called by cb_compute_order.c and c2am.c
*****************************************************************/
#include <stdio.h>
#include <malloc.h>
#include <float.h>
#include "clam.h"

#define LEFT 0
#define RIGHT 1
#define CENTRE 2
#define graphQuery messQuery

int Znum_merge=0, Znum_ctg0=0;
int ZburyFlag=2; /* 1= pseudo bury, 2=move ctg0 */
Graph g996, g969;
void okMenu(), okAllMenu();

extern void show_help();
extern void AutoCtgMsg(), ZautoCpM(), ZstoreCpM(), ZrestoreCpM();
extern int ZscoreCpM(struct tmpCz*, struct tmpCz*,struct tmpSz*);
extern BOOL movedone;
extern void recalcorder(), move_selected(), bury();
extern void showClam(), clearMsg(), append_remark();
extern void updateproj(), refreshlist(), Zgetmatch(struct tmpCz*,struct tmpCz*, struct tmpSz*), Zsel_allbury();
extern int loadCzfast();
extern void unbury(), sel_bur(), quitCB(), after_contigs_changed();
extern int child_adjustment(), init_CpM(), Zaddcomment(), print_CpMcnts();

static int reportFlag=0, mvDisCtgFlag=0;
static int burry;
static int last_z, gap_bet_ctgs=10; /* gap between contigs */
static void flip_zset(), save_selected(), redo_selected(),  print_report();
static void setup_and_place_Zsets(), add_match(), sort_zmx(), add_N();
static void place_all(), fake_setup();
static int look_right(), look_left();
static int first_left, last_x;

static void zhelp() {
show_help("/Compute CBmap/CBmap display/OK","okall");
}

/****************************************************************
                 DEF: remove_fp_remark
this is called by OK_All, which is called from Build Contigs. 
it is also called from CBlayout, which is called after Zcalc_zap.
in all cases, the CB algorithm has been run, so previous joins are 
no longer valid. The "CB-merge" is appended in this file, whereas
the "End-merge" is appended in Ends2Ends, which does not call the
CB routine.
*****************************************************************/
static void remove_fp_remark()
{
  struct remark *fp,*prev;
  CLONE *clone;
  int i;

  for (i=0; i<ZZ.size; i++)
  {
     clone = arrp(acedata,ZZ.matrix[i].cin,CLONE);
     prev = NULL;
     for (fp = clone->fp_remark; fp != NULL; fp = fp->next)
     {
        if (strstr(fp->message,"CB-merge")!=NULL || strstr(fp->message,"End-merge")!=NULL)
        {
            if(fp->next == NULL){ /* last */
               if (prev == NULL) clone->fp_remark = NULL;
               else prev->next = NULL;
            }
            else if (prev == NULL) { /* first */
               clone->fp_remark = fp->next;
            }
            else{
               prev->next = fp->next;
            }
        }
        else prev = fp;
     }
  }
}
/*********************************************************************
                 DEF: Zdo_coords
use by all oks 
********************************************************************/
int Zdo_coords(int i, int off, int flag, int z)
{
CLONE *clone;
int x, j,  len, len1, len2;
int left, right, tog, diff;
int p=PRTMESS;

       x=5;           /* determine if on end */
       if (Zset[z].n_clone==2) {
          if (Zset[z].csort[0].i == i) x = 0;
          else x = 1;
       }
       else if (ZZ.matrix[i].leftb==Zset[z].leftb && 
           ZZ.matrix[i].rightb!=Zset[z].rightb) x=3;
       else if (ZZ.matrix[i].leftb!=Zset[z].leftb && 
                ZZ.matrix[i].rightb==Zset[z].rightb) x=4;

       clone = arrp(acedata, ZZ.matrix[i].cin, CLONE);
       clone->selected = 1;
       if (ZZ.matrix[i].mtype & IAM_CHILD && clone->match[0] == ' ')
       {
              PRTMESS=0;
              j = ZZ.matrix[i].high_match;
              bury(ZZ.matrix[i].cin, ZZ.matrix[j].cin);
              PRTMESS=p;
              burry++;
       }
       if (flag==0) { /* CBcoords */
            clone->x = ZZ.matrix[i].leftb;
            clone->y = ZZ.matrix[i].rightb;
            return clone->y; 
       }
           /* NB I tried just using midpt+/- nbands/2, did not work as well */

                            /* Len=Bands */
       len = clone->fp->b2;
       if (x==0) {      /* size = 2, extend left */
           clone->x = ZZ.matrix[i].leftb +off;
           clone->y = ZZ.matrix[i].leftb + (len-1) +off;
           return clone->y; 
       }
       if (x==1) { /* size = 2, extend right */
           clone->x = (ZZ.matrix[i].rightb - (len-1)) +off;
           clone->y = ZZ.matrix[i].rightb +off;
           return clone->y; 
       }

        j = abs(ZZ.matrix[i].rightb - ZZ.matrix[i].leftb)+1;
        diff = len - j;
        left = ZZ.matrix[i].leftb;
        right = ZZ.matrix[i].rightb;
        if (diff < 0) {
            tog = (x==4) ? 1 : 0;
            for (; diff < 0; diff++) {
                if (tog) left++;
                else right--;
                tog = !tog;
            }
         }
         else if (diff==2) { /* the two ends */
             left--;
             right++;
         }
         else {
             if (x==3) { 
                 len1=2; len2=1; tog=1;
             }
             else if (x==4) { 
                 len1=1; len2=2; tog=0;
             } 
             else {
                 len1=1; len2=1; tog=0;
             }
             while (diff > 0) { 
                 if (tog) {
                     left -= len1;
                     diff -= len1;
                     if (diff < 0) left++;
                 }
                 else  {
                     right+= len2;
                     diff -= len2;
                     if (diff < 0) right--;
                 }
                 tog = !tog;
              } 
          }
          clone->x = left +off;
          clone->y = right +off;

                                 /* Left End, used by Fp and Gel order */
       if (flag==2 && last_x!=INT_MIN) {        
          while (clone->x <= last_x+1) {
            clone->x++;
            clone->y++;
          }
       }

       last_x = clone->x;
         
return clone->x; 
}

/********************************************************************
                      OKALL on Ok window
********************************************************************/
static int look_left(), look_right();
static void place_Zset(), scanOK();

static int N, max_N;
static struct ze {
  int z, cin; 
  int z_map;  /* index into Zset, which is a cbmap */
  int orient; 
} *Zend;

#define OX 3  /* left, right, abuts both ends */
#define NX 10  /* allow NX ends of of each OX type */

struct zmx {
     int z_neigh; /* index into Zset/Zmap of abutting cbmap*/ 
     int o;       /* orintation */
     int cin1, cin2;  /* high scoreing end clone in acedata */
     int z1, z2;      /* into Zmatrix and SS */
     int accum_score; 
     int best_score; 
     int num_matches; 
};
static struct zm {
   int next, flip;
   int done;
   int z1, z2;
   struct zmx end[OX][NX];
} *Zmap;     /* 1-to-1 with Zset */

static struct save_sel {
  int cin, ends_sel, ctg, real_sel;
} *SS;       /* 1-to-1 with ZZ.matrix */

static int NC;

static int right_end, match, bridge;

/********************************************************************
                       DEF: CBlayout
called after Zcalc_zap for the following:
called from c2am.c during Ends->Ends with Auto
                          Reanalyzing contigs with no Qs 
                          DQing - can break into multiple contigs
Called from OKAll on CBmap window 
  this can create multiple contigs
The 'currentctg' is being analyzed.

qstuff set in DQer or Reanalyze or Ends->Ends
qstuff_nosplit set in Reanalyze - maybe mult cbmaps, but don't split
********************************************************************/
void CBlayout()
{
int save_c, cnt, n, i, j,  c, k, x;
CLONE *clp;
int set, current_qs, new_qs, Zsel_bury();
char ctmp[500], ctmp2[MSGSIZE*2];

   if (n_Zset==0) return;
   if (graphActivate(g996)) {
       scanOK();
       graphDestroy();
   }
        /* mvDisCtgFlag can also be set in OKALL menu */
   if(qstuff && !qstuff_nosplit) mvDisCtgFlag=1; 
   else if(qstuff && qstuff_nosplit) mvDisCtgFlag=0;  

   remove_fp_remark();
   SS = NULL;
   save_selected();
   bridge=right_end =0;
   burry=0;

                  /* only one CBmap */
   if (n_Zset==1) {
      if (LastCB==Fp_order || LastCB==Gel_order) {
          x =2;
          last_x = INT_MIN;
      } else x=1;

      for (c=0; c < Zset[0].n_clone; c++) 
      {
         i = Zset[0].csort[c].i;
         Zdo_coords(i, -Zset[0].leftb, x, 0);
         SS[i].ctg = 0;
      }
      NC=1;
   }
   else if (LastCB==DQ && Pz.DQsplit==1) fake_setup();
   else setup_and_place_Zsets();

   if (LastCB==Fp_order || LastCB==Gel_order) goto MOVE;

                /* Bury Ignored or move to ctg0 */
   for (cnt=c=0,i=0; i < ZZ.size; i++) {
      clp = arrp(acedata, ZZ.matrix[i].cin, CLONE);
      if (ZZ.matrix[i].cbmap == ZIGNORED && SS[i].ends_sel==0)
      {    
          if (ZburyFlag>0) {
             clp->x = clp->y = -50;
             clp->selected = TRUE;
          }
          cnt++;
      }
      else clp->selected = FALSE;
   }
   PRTMESS=0;
   if (cnt > 0) {
      if (ZburyFlag==1)  {
          n = Zsel_bury();
          sprintf(ctmp,"Pseudo %d",cnt);
      }
      else if (ZburyFlag==2) {
          move_selected(currentctg, 0, 0);
          sprintf(ctmp,"Move to Ctg0 %d",cnt);
          Znum_ctg0+=cnt;
      }
      else sprintf(ctmp,"End %d",cnt);
   }
   else ctmp[0]='\0';
   
   sprintf(ZBuf,
     "OKALL: CBmaps %d Merge %d Contig %d.  Singles %d: Bridge %d %s\n",
          n_Zset, n_Zset-NC, NC, Ignored_clones, bridge, ctmp); Outlog;
   if (!qstuff) { 
      sprintf(ZBuf,"CBmaps %d Merge %d Contig %d %s",n_Zset, n_Zset-NC, NC,ctmp); 
      showClam(); 
   }
   if (NC>1) Znum_merge++; 
 
MOVE: ;
   strcpy(ctmp,"CB-merge");
                       /* do moves for currentctg only */
   for (save_c=current_qs=i=0; i < ZZ.size; i++) {
       clp = arrp(acedata, ZZ.matrix[i].cin, CLONE);
       if (clp->ctg!=currentctg) clp->selected = FALSE;
       else if (!mvDisCtgFlag && 
               (ZZ.matrix[i].cbmap >= 0 || SS[i].ends_sel>=1)) 
                                {clp->selected = TRUE; save_c++;}
       else if (SS[i].ctg == 0) {clp->selected = TRUE; save_c++;}
       else  clp->selected = FALSE;
       if (clp->selected && ZZ.matrix[i].cbQ == QALIGN) current_qs++;
       if (SS[i].ends_sel) append_remark(ZZ.matrix[i].cin, ctmp);
    }
    PRTMESS=0;
    if (Pz.offset!=0) printf("Starting coordinate %d\n",Pz.offset);
    move_selected(currentctg, currentctg, Pz.offset); /*cari 15apr05 add offset */
    Pz.offset=0;
    ctmp[0]='\0';

    if (!mvDisCtgFlag || NC == 1) goto DONE;
   
                         /* move disconnected contigs to new contigs */
    n = getcontigsmax();
    for (j=1; j < NC; j++) {
          k = INT_MAX;
          for (new_qs=c=i=0; i < ZZ.size; i++) {
              clp = arrp(acedata,SS[i].cin,CLONE);
             if (SS[i].ctg == j && clp->ctg==currentctg) {
                  /* is only less than if IGNORED, should never be greater than n_Zset */
                  if (ZZ.matrix[i].cbmap > 0 && ZZ.matrix[i].cbmap <= n_Zset)
                      set = ZZ.matrix[i].cbmap;  /* same for all in j */
                  clp->selected = TRUE;
                  k = MiN(k,clp->x);
                  c++;
                  if (ZZ.matrix[i].cbQ == QALIGN) new_qs++;
                  if (SS[i].ends_sel) append_remark(ZZ.matrix[i].cin, ctmp);
              }
              else arrp(acedata,SS[i].cin,CLONE)->selected = 0;
          }
          move_selected(currentctg, n+j, -k);

              /* annotation for new contig */
          sprintf(ZBuf,"Move %d clones from ctg%d to ctg%d\n",
                                         c, currentctg, n+j); Outlog;
          sprintf(ctmp,"%s From ctg%d", Fn, currentctg);

              
          if (set > 0 && set <= n_Zset && c == Zset[set].n_clone) {
             contigs[n+j].approxQs = 0; 
             contigs[n+j].ctgQs = Zset[set].n_Qs; 
             contigs[n+j].high_score = Zset[set].score*1000;
             contigs[n+j].avg_score = Zset[set].avg*1000;
             contigs[n+j].low_score = Zset[set].low*1000;
             sprintf(ctmp2,"NoSplit %1.e.", Pz.cutFlt);
          }
          else {
             contigs[n+j].approxQs = 1;
             contigs[n+j].ctgQs = new_qs; 
             sprintf(ctmp2,"Map>1 Qs%d.", new_qs);
          }
          sprintf(contigs[n+j].projmsg, "%s %s",ctmp, ctmp2);
          AutoCtgMsg(n+j,ctmp);
          
          if (!Zbatch_flag && graphInterruptCalled()) {
              printf("User Interrupt - pre-mature termination of OK All\n");
              break;
          } 
    }
/* annotation for current contigs with splits*/
    if (!qstuff) printf("Moved %d contigs. Removing CBmap window\n", j-1);

    if (n+1 == n+j-1) { 
       sprintf(ctmp,"%s Split ctg%d %0.e", Fn, n+1, Pz.cutFlt);
    }
    else if (n+1 < n+j-1) { 
       sprintf(ctmp,"%s Split ctg%d-ctg%d %0.e", Fn, n+1, n+j-1, Pz.cutFlt);
    }
    else ctmp[0] = '\0';

DONE: ;
/* annotation for current contig - do after all moves */
    strncpy(ctmp2, contigs[currentctg].projmsg,MSGSIZE-40);
    if (ctmp[0]=='\0') { 
       if (LastCB==Fp_order || LastCB == Gel_order)
           sprintf(ctmp,"%s %d clones", Fn, Zset[0].n_clone);
       else 
           sprintf(ctmp,"%s NoSplit %0.e", Fn, Pz.cutFlt);
    }
    sprintf(ctmp2,"%s.",ctmp);
    AutoCtgMsg(currentctg,ctmp2);
    contigs[currentctg].ctgQs = current_qs;
    contigs[currentctg].approxQs = 1;

    if (!mvDisCtgFlag && NC > 1) { /* run from Reanalysis or OKALL */
        sprintf(ctmp2,"%s Map%d. %s ", ctmp, NC, contigs[currentctg].projmsg);
        strncpy(contigs[currentctg].projmsg,ctmp2,MSGSIZE-1);
    }
    else if (LastCB==Fp_order || LastCB==Gel_order || LastCB==Select) { 
        sprintf(contigs[currentctg].projmsg,"%s %d clones.",Fn, Zset[0].n_clone);
    }
    else if (save_c != Zset[0].n_clone) {
        sprintf(ctmp2,"%s Map>1 Qs%d. %s",
                     ctmp, current_qs,contigs[currentctg].projmsg);
        strncpy(contigs[currentctg].projmsg,ctmp2,MSGSIZE-1);
    }
    else if (save_c == Zset[0].n_clone) {
        if (LastCB!=IBC) { /* IBC gives it own message */
           sprintf(ctmp2,"%s Map1 Qs%d. %s",
                ctmp,  current_qs, contigs[currentctg].projmsg);
           strncpy(contigs[currentctg].projmsg,ctmp2,MSGSIZE-1);
        }
        contigs[currentctg].ctgQs = Zset[0].n_Qs; 
        contigs[currentctg].approxQs = 0; 
        contigs[currentctg].high_score = Zset[0].score*1000;
        contigs[currentctg].avg_score = Zset[0].avg*1000;
        contigs[currentctg].low_score = Zset[0].low*1000;
    }
    else { 
        strncpy(contigs[currentctg].projmsg,ctmp2,MSGSIZE-1);
    }
    PRTMESS=1;
    movedone=newctg=TRUE;
    newsettings=FALSE;
    
    if (currentctg!=0) {
      if (contigs[currentctg].count == 0) 
          printf("Contig %d no longer has any clones\n",currentctg);
             /* if the current contig is empty, the display will be killed*/
      ctgdisplay(currentctg);  
      redo_selected();
      //quitCB();
    }
    refreshlist();
    updateproj();
    
    if (SS!=NULL) free(SS);
}
/*****************************************************************
      various routines for CBlayout to compute layout
*****************************************************************/
/***********************************************************************
                       DEF: fake_setup
************************************************************************/
static void fake_setup()
{
int i;

   for (i=0; i<ZZ.size; i++) 
      SS[i].ctg = ZZ.matrix[i].cbmap;
   
   NC = n_Zset;
}
/***********************************************************************
                       DEF: setup_and_place_Zsets
***********************************************************************/
static void setup_and_place_Zsets()
{
int n, i, j, z, c;
int  left_sp, right_sp;
int score;
double tmpCut;

   N=0;
   max_N = n_Zset*5 + Ignored_clones;
   Zend = (struct ze *) malloc(sizeof(struct ze)*max_N);
   NOMEM2(Zend, "Zend");

   Zmap = (struct zm *) malloc(sizeof(struct zm)* (n_Zset+Ignored_clones+2));
   NOMEM2(Zmap, "Zmap");
   for (z=0; z< n_Zset+Ignored_clones+2; z++) {
      Zmap[z].done = 0; Zmap[z].next = -1;
      for (i=0; i< OX; i++) 
        for (j=0; j< NX; j++) {
            Zmap[z].end[i][j].accum_score =  0;
            Zmap[z].end[i][j].best_score =  0;
            Zmap[z].end[i][j].num_matches =  1;
            Zmap[z].end[i][j].z_neigh =  -1;
            Zmap[z].end[i][j].o =  CENTRE;
            Zmap[z].end[i][j].cin1 = Zmap[z].end[i][j].cin2 = -1;
            Zmap[z].end[i][j].z1 = Zmap[z].end[i][j].z2 = -1;
        }
   }
   NC=0;

   scanOK();
   tmpCut = Pz.cutFlt;
   Pz.cutFlt = ZZ.cutOK;
   if (Cp.useFlag) {
        ZstoreCpM(); 
        ZautoCpM(0);
        if (!init_CpM(0)) return;
   }
   if (!qstuff) {
       sprintf(ZBuf,"Cutoff %.0e. Distance from ends %d.\n", 
          Pz.cutFlt, Pz.fromendInt); Outlog;
   }
              /** find end clones; add_N also adds buried clones **/
   for (z=0; z< n_Zset; z++)
   {
            /* a CBmap can be moved to a differnt contig by Accept */
      if (Zset[z].ctg!=0 && Zset[z].ctg!=currentctg) continue; 
      for (c=0; c < Zset[z].n_clone; c++) 
      {
         i = Zset[z].csort[c].i;
         if (arrp(acedata, ZZ.matrix[i].cin, CLONE)->ctg!=currentctg) continue;
 
         left_sp = abs(ZZ.matrix[i].leftb - Zset[z].leftb);
         right_sp = abs(ZZ.matrix[i].rightb - Zset[z].rightb);
         if (left_sp <= Pz.gap && right_sp <= Pz.gap ) add_N(z, i,CENTRE);
         else if (left_sp <= Pz.fromendInt && left_sp < right_sp) add_N(z, i,LEFT);
         else if (right_sp <= Pz.fromendInt)add_N(z, i,RIGHT);
       }
    }
    n=N;
              /** add Ignored clones **/
             
    if (Ignored_clones && n_Zset>1)
      for (i=0; i<ZZ.size; i++) 
         if (ZZ.matrix[i].cbmap == ZIGNORED) 
            add_N(z++, i, CENTRE);
    
              /** compare end clones based on all bands in clone **/
    for (i=0; i<n-1; i++) /* do all CBmaps first */
    {
       loadCzfast(&C1z, Zend[i].cin); 
       for (j=i+1; j<n; j++)
       {
          if (Zend[i].z_map == Zend[j].z_map) continue;
          loadCzfast(&C2z, Zend[j].cin); 
          Zsulston(&C1z,&C2z,&Sz);
          score= ZscoreCpM(&C1z,&C2z,&Sz);
          if (score > 0) {
             add_match(j,i, score); 
             add_match(i,j, score);
          }
       }
    }
    for (i=0; i<N-1; i++)  /* now do Ignored */
    {
       loadCzfast(&C1z, Zend[i].cin); 
       j = (i>=n_Zset) ?  i+1 : n_Zset;
       for (; j<N; j++)
       {
          if (Zend[i].z_map == Zend[j].z_map) continue;
          loadCzfast(&C2z, Zend[j].cin); 
          Zsulston(&C1z,&C2z,&Sz);
          score= ZscoreCpM(&C1z,&C2z,&Sz);
          if (score > 0) {
             add_match(j,i, score); 
             add_match(i,j, score);
          }
       }
    }
    for (i=n_Zset; i< n_Zset+Ignored_clones; i++) {
          if (Zmap[i].end[CENTRE][1].z_neigh == -1) {
              Zmap[i].end[CENTRE][0].z_neigh = -1;
              Zmap[i].done = 1;
          }
    }
    for (z= 0; z < n_Zset+Ignored_clones; z++) {
       if (Zmap[z].end[0][0].z_neigh!=-1) sort_zmx(z,0);
       if (Zmap[z].end[1][0].z_neigh!=-1) sort_zmx(z,1);
       if (Zmap[z].end[2][0].z_neigh!=-1) sort_zmx(z,2);
    }
    print_report();
                 /** place CBmaps **/
   while(1)
   {
      last_z = -2;
      for (score=-1, n=i=z=0; i< n_Zset; i++) {
        if (Zmap[i].done) continue;
        for (j=0; j<OX; j++)
            if (Zmap[i].end[j][0].accum_score >= score) {
              score = Zmap[i].end[j][0].accum_score;
              z = i;
            }
      }
      if (score== -1) break;

      if (reportFlag) printf("Start%d: \n",z+1);
      Zmap[z].done = 1;

      look_left(z, 0);
      look_right(z, 1);
      place_all();

      NC++;

      if (reportFlag) printf("\n");
      right_end+= (gap_bet_ctgs+Pz.ok_olap);
      if (graphInterruptCalled()) {
          printf("User Interrupt - pre-mature termination of OK ALL\n");
          break;
      } 
   }
   free(Zend);
   free(Zmap);

   Pz.cutFlt = tmpCut;
   if (Cp.useFlag) {
       print_CpMcnts(); Outlog;
       ZrestoreCpM(0);
   }
}
/***********************************************************************
                       DEF: place_Zset
***********************************************************************/
static void place_Zset(int z, int flip)
{
int i, i2, cin, off, rt, x, tmp, c, c2, found;
int save=right_end, left_end=INT_MAX;
CLONE *clp;
CLONE *clp2;
char xxx[3][6] = {"!flip", "flip", "-"};

      if (reportFlag) printf("%d-%s ",z+1, xxx[flip]);
      if (Zmap[z].next!=-1) {
        SS[Zmap[z].z1].ends_sel = 1;
        SS[Zmap[z].z2].ends_sel = 1;
        if (reportFlag) printf("(%s,%s)\n",
          arr(acedata,ZZ.matrix[Zmap[z].z1].cin, CLONE).clone,
          arr(acedata,ZZ.matrix[Zmap[z].z2].cin, CLONE).clone);
      }

      if (z >= n_Zset) /* Ignored clone */
      {
          bridge++;
          cin = Zmap[z].end[2][0].cin1; 
          clp = arrp(acedata,cin,CLONE);
          clp->x = right_end-Pz.ok_olap+1;
          clp->y = clp->x + clp->fp->b2;
          i = Zmap[z].end[2][0].z1; 
          SS[i].ctg = NC;
          if (ZZ.matrix[i].high_match != -1) {
              x = ZZ.matrix[i].high_match;
              SS[x].ctg = NC;
              SS[x].ends_sel = 1;
              clp = arrp(acedata,ZZ.matrix[x].cin,CLONE);
              clp->x = right_end-Pz.ok_olap+1;
              clp->y = clp->x + clp->fp->b2;
          } 
          right_end = clp->y; /* clp is parent */
          return;
      }
      if (Zset[z].n_clone==2) {
         x = Zset[z].csort[0].i;
         if (Zmap[z].z2 == x) { /* purify, uninitizlized memory read */
           Zset[z].csort[0].i = Zset[z].csort[1].i;
           Zset[z].csort[1].i = x;
         }
      }
      off = abs(Zset[z].leftb)+right_end+1;
      for (c=0; c< Zset[z].n_clone; c++)
      {  
         i = Zset[z].csort[c].i;
         if (Zset[z].n_clone!=2) 
         {
            if (flip==1) {
               rt = Zset[z].rightb+Zset[z].leftb;
               tmp = ZZ.matrix[i].leftb;
               ZZ.matrix[i].leftb = - ZZ.matrix[i].rightb + rt;
               ZZ.matrix[i].rightb = - tmp + rt;
            }
         }
         Zdo_coords(i, off, 1, z);
         clp = arrp(acedata,ZZ.matrix[i].cin,CLONE);

         /* If this clone was buried in a clone, and that clone isn't in
            this Zset, unbury it */
          if (clp->match[0]!=' ')  
          {
             found = 0;
             for (c2=0; c2< Zset[z].n_clone; c2++)
             {   
                 i2 = Zset[z].csort[c2].i;
                 clp2 = arrp(acedata,ZZ.matrix[i2].cin,CLONE);
                 if (0 == strcmp(clp->match, clp2->clone))
                 {
                     found = 1;
                     break;
                 }
             } 
             if (found == 0)
             {
                unbury(ZZ.matrix[i].cin);
             }
          }

            /* otherwise, when buried not shown, can have gap */
          if (clp->match[0]==' ')  {

            left_end = MiN(left_end, clp->x);
            right_end = MaX(right_end, clp->y);

          }   

         SS[i].ctg = NC;
      }

          /* the ends can extend passed Zset left and right */
      if (save==0) x = -left_end;
      else x = (save-left_end)-Pz.ok_olap;
          
      for (c=0; c< Zset[z].n_clone; c++)
      {  
         i = Zset[z].csort[c].i;
         clp = arrp(acedata,ZZ.matrix[i].cin,CLONE);
         clp->x += x;
         clp->y += x;
      }
      right_end += x;

      if (flip) flip_zset(z);
}
/***********************************************************************
                       DEF: place_all
***********************************************************************/
static void place_all()
{
int i;
int start, end;

/* remove ignored on ends */
   for (i=first_left; i != -1 && i >= n_Zset; i = Zmap[i].next);
   start = i;

   for (end=-1; i != -1; i = Zmap[i].next)
              if (i < n_Zset) end = i;

   if (end!=-1) Zmap[end].next = -1;

   for (i=start; i != -1; i = Zmap[i].next) 
          place_Zset(i, Zmap[i].flip);
}

/***********************************************************************
                       DEF: find_next_map
***********************************************************************/
static int find_next_map(int z, int o, int *next_z, int *next_o, int *z1, int *z2)
{
int n, k, i,j;
int l, r, c;
int nl=-1, nr=-1, nc=-1;
int sl, sr, sc;

      for (sl=l=-1, k=0; k<NX && sl== -1; k++) {
           l = Zmap[z].end[LEFT][k].z_neigh;
           if (l!=-1 && !Zmap[l].done) {
             sl = Zmap[z].end[LEFT][k].accum_score;
             nl = k;
           }
      }
      for (sr=r=-1, k=0; k<NX && sr== -1; k++) {
           r = Zmap[z].end[RIGHT][k].z_neigh;
           if (r!=-1 && !Zmap[r].done) {
             sr = Zmap[z].end[RIGHT][k].accum_score;
             nr = k;
           }
      }
      for (sc=c=-1, k=0; k<NX && sc== -1; k++) {
           c = Zmap[z].end[CENTRE][k].z_neigh;
           if (c!=-1 && !Zmap[c].done) {
             sc = Zmap[z].end[CENTRE][k].accum_score;
             nc = k;
           }
      }
      if  (o==LEFT) {
         if (sl > sc)       {i=l; o=LEFT; n=nl;}
         else if (sc != -1) {i=c; o=CENTRE; n=nc;}
         else return 0;
      }
      else if  (o==RIGHT) {
         if (sr > sc)       {i=r; o=RIGHT; n=nr;}
         else if (sc != -1) {i=c; o=CENTRE; n=nc;}
         else return 0;
      }
      else {
         if (sr > sc && sr > sl) {i=r; o=RIGHT; n=nr;}
         else if (sl > sc && sl > sr) {i=l; o=LEFT; n=nl;}
         else if (sc != -1)      {i=c; c=CENTRE;  n=nc;}
         else return 0;
      }
      Zmap[i].done=1;
      *next_z = i;
      *next_o = Zmap[z].end[o][n].o;

      *z1 = Zmap[z].end[o][n].z1;
      *z2 = Zmap[z].end[o][n].z2;
      if (reportFlag) {
         i=j=1; 
         if (z<n_Zset) i = Zset[z].n_clone;
         if (*next_z<n_Zset) j = Zset[*next_z].n_clone;
         printf("CB%-2d CB%-2d orient %d %d size %3d %-3d score %3d %12s %12s\n", 
              z+1, *next_z+1, o, *next_o, i, j,
              Zmap[z].end[o][n].accum_score,
              arr(acedata, Zmap[z].end[o][n].cin1, CLONE).clone, 
              arr(acedata, Zmap[z].end[o][n].cin2, CLONE).clone);
       }
      return 1;
}
/***********************************************************************
                       DEF: look_left
***********************************************************************/
static int look_left(int z, int o, int first)
{
int next_z, next_o;
int end[3]={1,0,2};
int z1, z2;
   
    if (find_next_map(z, o, &next_z, &next_o, &z1, &z2)) {
        Zmap[next_z].next = z;
        Zmap[next_z].flip = end[next_o];
        Zmap[next_z].z1 = z1;
        Zmap[next_z].z2 = z2;
        look_left(next_z, end[next_o], 0);
    } else first_left = z;
    
return 1;
}
/***********************************************************************
                       DEF: look_right
***********************************************************************/
static int look_right(int z, int o, int first)
{
int next_z, next_o;
int end[3]={1,0,2};
int z1, z2;
   
    if (find_next_map(z, o, &next_z, &next_o, &z1, &z2)) {
        Zmap[z].next = next_z;
        look_right(next_z, end[next_o], 0);
    }
    Zmap[z].flip = end[o];
    Zmap[z].z1 = z1;
    Zmap[z].z2 = z2;

return 1;
}
/*****************************************************************
       various  CBlayout utility routines
*****************************************************************/
/**************************************************************
                    DEF: add_N()
***************************************************************/
static void add_N(int z, int i, int o)
{
     if (N >= max_N) {
        max_N += 100;
        Zend = (struct ze *) realloc(Zend, sizeof(struct ze)* max_N);
        NOMEM2(Zend, "Zend");
     }
     Zend[N].cin = ZZ.matrix[i].cin;
     Zend[N].z = i;
     Zend[N].z_map = z;
     Zend[N].orient = o;
     N++;
}
/**************************************************************
                    DEF: sort_zmx()
***************************************************************/
static void sort_zmx(int z, int o)
{
int i,j;
struct zmx tmp;

  for (i=0; i<NX-1; i++)
    for (j=i+1; j<NX; j++) 
        if (Zmap[z].end[o][i].accum_score < Zmap[z].end[o][j].accum_score) {
           tmp = Zmap[z].end[o][i]; 
           Zmap[z].end[o][i] = Zmap[z].end[o][j]; 
           Zmap[z].end[o][j] = tmp; 
        }
  for (i=0; i<NX-1; i++)
    for (j=i+1; j<NX; j++) 
        if (Zmap[z].end[o][i].z_neigh >= n_Zset && Zmap[z].end[o][i].z_neigh < n_Zset) {
           tmp = Zmap[z].end[o][i]; 
           Zmap[z].end[o][i] = Zmap[z].end[o][j]; 
           Zmap[z].end[o][j] = tmp; 
        }
}
/**************************************************************
                    DEF: add_match()
***************************************************************/
static void add_match(int i, int j, int score)
{
int z, o, k, n, s;

     z = Zend[i].z_map; 
     o = Zend[i].orient;

     n = s = -1;
     for (k=0; k<NX && n== -1; k++) {
        if (Zmap[z].end[o][k].z_neigh == Zend[j].z_map) {
           if (Zend[i].z_map < n_Zset && Zend[j].z_map < n_Zset)
               Zmap[z].end[o][k].accum_score += score;
           else Zmap[z].end[o][k].accum_score++;
           Zmap[z].end[o][k].num_matches++;
           if (Zmap[z].end[o][k].best_score < score) n=k;
           s = -1;
           break;
        }
        else
           if (Zmap[z].end[o][k].z_neigh == -1)  {
              Zmap[z].end[o][k].accum_score = score;
              n=k; s = -1;
           }
        else 
           if (Zend[j].z_map >= n_Zset) {
              if (Zmap[z].end[o][k].z_neigh >= n_Zset && Zmap[z].end[o][k].accum_score < score) {
                 if  (s==-1) s=k; 
                 else if (Zmap[z].end[o][k].accum_score < Zmap[z].end[o][s].accum_score) s=k;
              }
           }
           else {
              if (Zmap[z].end[o][k].accum_score < score) {
                if  (s==-1) s=k; 
                else if (Zmap[z].end[o][k].accum_score < Zmap[z].end[o][s].accum_score) s=k;
              }
           }
     } 
     if (n==-1 && s == -1) return;
     if (n==-1) {
        n = s;
        Zmap[z].end[o][n].accum_score=score;
     }
     Zmap[z].end[o][n].best_score = score;
     Zmap[z].end[o][n].cin1 = Zend[i].cin;
     Zmap[z].end[o][n].cin2 = Zend[j].cin;
     Zmap[z].end[o][n].z1 = Zend[i].z;
     Zmap[z].end[o][n].z2 = Zend[j].z;
     Zmap[z].end[o][n].z_neigh = Zend[j].z_map; 
     Zmap[z].end[o][n].o = Zend[j].orient;
     match++;
}
/**************************************************************
                    DEF: save_selected()
***************************************************************/
static void save_selected()
{
int i;

   SS = (struct save_sel *) 
         malloc(sizeof(struct save_sel) * ZZ.size);
   NOMEM2(SS,"SS Next");

   for (i=0; i<ZZ.size;  i++) {
       SS[i].ctg = -1;
       SS[i].ends_sel = 0;
       SS[i].cin = ZZ.matrix[i].cin;
       SS[i].real_sel = arrp(acedata,ZZ.matrix[i].cin,CLONE)->selected;
       arrp(acedata,ZZ.matrix[i].cin,CLONE)->selected = 0;
   }
}
/**************************************************************
                    DEF: redo_selected()
***************************************************************/
static void redo_selected()
{
int i;
void ZhighCin();
CLONE *clp;

   for (i=0; i<ZZ.size;  i++) {
       clp = arrp(acedata,SS[i].cin,CLONE);
       if (clp->ctg == currentctg) {
          clp->selected = SS[i].real_sel;
          if (SS[i].ends_sel>0) ZhighCin(CLAM, SS[i].cin);
          else if (clp->selected) ZhighCin(SELECTED, SS[i].cin); 
       }
   }
}
/**************************************************************
                    DEF: print_report()
***************************************************************/
static void print_report()
{
int  i, j, z;
char x1,  s1[20], s2[20];
char how[3][10]={"left  ", "right ", "either"};

    if (reportFlag) {
      printf("\nCB  CB   Accum  Cnt  orient  orient \n");
      for (z=0; z< n_Zset+Ignored_clones; z++) {
         x1='*';
         for (i=0; i< OX; i++) {
           for (j=0; j< NX; j++) {
             if (Zmap[z].end[i][j].accum_score > 0) {
                  strcpy(s1,arrp(acedata, Zmap[z].end[i][j].cin1,CLONE)->clone);
                  strcpy(s2,arrp(acedata, Zmap[z].end[i][j].cin2,CLONE)->clone);
                  printf("%c CB%-3d CB%-3d %3d %2d %s %s %12s %12s\n",
                   x1, z+1, Zmap[z].end[i][j].z_neigh+1, 
                   Zmap[z].end[i][j].accum_score,
                   Zmap[z].end[i][j].num_matches,
                   how[i],  how[Zmap[z].end[i][j].o], s1, s2);
                  x1=' ';
             }
             else break;
           }
         }
      }
    }
}

/************************************************************************
                       DEF: OK_Zset
cb_compute_order.c, Build Contigs
************************************************************************/
void OK_Zset(int from, int to)
{
int  i, c;
int  x, left_off, off;
extern void Start_timer(), End_timer();
CLONE *clp;

PRTMESS=0;

   if (n_Zset==0) {
      printf("No CBmaps.\n");
      return;
   }
   remove_fp_remark();

   Zset[ZS].ctg = to;
   off = abs(Zset[ZS].leftb);
   left_off =0;
   for (c=0; c< Zset[ZS].n_clone; c++) {
      i = Zset[ZS].csort[c].i;
      x = Zdo_coords(i,off, 1, ZS);
      left_off = MiN(left_off, x);
   }
   for (c=0; c< Zset[ZS].n_clone; c++) {
      i = Zset[ZS].csort[c].i;
      clp = arrp(acedata, ZZ.matrix[i].cin, CLONE);
      if (clp->match[0]!=' ') { 
         if (child_adjustment(arrp(acedata,clp->parent,CLONE), clp))
            left_off = MiN(left_off, clp->x);
      }
   }
   move_selected(from, to, abs(left_off));
   contigs[currentctg].ctgQs = Zset[ZS].n_Qs; 
   contigs[currentctg].approxQs = 0; 
   contigs[currentctg].high_score = Zset[ZS].score*1000;
   contigs[currentctg].avg_score = Zset[ZS].avg*1000;
   contigs[currentctg].low_score = Zset[ZS].low*1000;
   sprintf(contigs[currentctg].projmsg,"%-4d %-6.3f %-6.3f %-6.3f",
             Zset[ZS].n_Qs, Zset[ZS].score, Zset[ZS].avg, Zset[ZS].low);
     
   for (c=contigs[to].start;  c != -1; c = arrp(acedata, c, CLONE)->next) 
         arrp(acedata, c, CLONE)->selected = 0;
PRTMESS=1;
}
/****************************************************************************
              Routines for the bottom half of the OK menu
***************************************************************************/
/****************************************************************************
                    DEF: flip_zset
***************************************************************************/
static void flip_zset(int z)
{
int i, j, c, rt;

    rt = Zset[z].rightb+Zset[z].leftb;
    for (c=0; c< Zset[z].n_clone; c++)
    {  i = Zset[z].csort[c].i;
       j = ZZ.matrix[i].leftb;
       ZZ.matrix[i].leftb = - ZZ.matrix[i].rightb + rt;
       ZZ.matrix[i].rightb = - j + rt;
    }
}
/*********************************************************
                   okMenu begin
*********************************************************/
static char dText[14], endText[14], minText[14], offText[14];
static int endBox, dBox, minBox, offBox;
static int  reportArc, ctgArc;
static int bury1Arc, bury2Arc;

static void scanOK()
{
  sscanf(dText,"%d",&Pz.ok_olap);
  sscanf(endText,"%d",&Pz.fromendInt);
  sscanf(minText,"%lf",&ZZ.cutOK);
  sscanf(offText,"%d",&Pz.offset);
}

static void pickg9(int box,double x,double y)
{
  if(box == dBox) dBox = graphTextEntry(dText,8,0,0,NULL);
  else if(box == endBox) endBox = graphTextEntry(endText,8,0,0,NULL);
  else if(box == minBox) minBox = graphTextEntry(minText,8,0,0,NULL);
  else if(box == offBox) minBox = graphTextEntry(offText,8,0,0,NULL);
  else if (box == bury1Arc) {
    ZburyFlag = 1;
    okMenu();
  }
  else if (box == bury2Arc) {
    ZburyFlag = 2;
    okMenu();
  }
  else if (box == reportArc) {
    reportFlag = (!reportFlag);
    okMenu();
  }
  else if (box == ctgArc) {
    mvDisCtgFlag = (!mvDisCtgFlag);
    okMenu();
  }
}

/***********************************************************
                       DEF: okMenu
************************************************************/
void okMenu()
{
float row=1.0, col1=2.0;
static MENUOPT amenu[] = { {graphDestroy, "Reject"}, {0, 0 }};
static int  n;
void scanOK();

  if (LastCB!=Build && ZZ.ctg!=currentctg) {
     printf("Error: shouldn't be instantiating contig %d (current %d)\n",
                ZZ.ctg, currentctg);
     return;
  }
  if (merging) {
     printf("Cannot OK when merging.\n");
     return;
  }
  if(graphActivate(g996)){   
    graphPop();
  }
  else{
    g996 = graphCreate (TEXT_FIT,"Instantiate CBmap",.2,.2,.45,.26) ;
    graphRegister (PICK, pickg9) ;

    n = getcontigsmax()+1;
    if (ZZ.ctg==0) Pz.ctg = n;
    else Pz.ctg =  currentctg;
    sprintf(dText, "%d", Pz.ok_olap); 
    sprintf(endText, "%d", Pz.fromendInt);
    sprintf(minText, "%.0e", ZZ.cutOK);
    sprintf(offText,"0");
    mvDisCtgFlag=0;
  }
  graphClear();
  graphMenu(amenu);

  graphText(">> Instantiate all CBmaps in Current Contig <<",2.0,row);
  row += 2.0;

  bury1Arc = graphBoxStart();
      graphArc(2.0, row+0.5, 0.7, 0, 360); 
      if (ZburyFlag==1) graphFillArc(2.0, row+0.5, 0.4, 0, 360);
      graphBoxEnd();
      graphBoxDraw(bury1Arc, BLACK, TRANSPARENT);
  graphText("Bury Singles as Pseudo",3.0,row);
  row += 1.5;

  bury2Arc = graphBoxStart();
      graphArc(2.0, row+0.5, 0.7, 0, 360); 
      if (ZburyFlag==2) graphFillArc(2.0, row+0.5, 0.4, 0, 360);
      graphBoxEnd();
      graphBoxDraw(bury2Arc, BLACK, TRANSPARENT);
  graphText("Move Singles to Ctg0",3.0,row);
  row += 2.0;

  graphText("Distance FromEnd to qualify as end clone:",col1,row);
  endBox = graphTextEntry(endText, 6, 44, row,scanOK);
  row += 2.0;
  graphText("Cutoff for matching end clones:",col1,row);
  minBox = graphTextEntry(minText, 6, 44, row,scanOK);
  row += 2.0;
  graphText("Overlap between adjacent CBmaps:",col1,row);
  dBox = graphTextEntry(dText, 6, 44, row,scanOK);

  row += 2.0;
   ctgArc = graphBoxStart();
      graphArc(6.0, row+0.5, 0.7, 0, 360); 
      if (mvDisCtgFlag) graphFillArc(6.0, row+0.5, 0.4, 0, 360);
      graphBoxEnd();
      graphBoxDraw(ctgArc, BLACK, TRANSPARENT);
   graphText("Move unconnected to new contigs",7.0,row);
  row += 2.0;
  graphButton("Ok All",CBlayout,2.0,row);
  graphButton("Reject",graphDestroy,10.0,row);

   reportArc = graphBoxStart();
      graphArc(20.0, row+0.5, 0.7, 0, 360); 
      if (reportFlag) graphFillArc(20.0, row+0.5, 0.4, 0, 360);
      graphBoxEnd();
      graphBoxDraw(reportArc, BLACK, TRANSPARENT);
   graphText("Report to Stdout",21.0,row);

  graphButton("Help",zhelp,44.0,row);

  graphRedraw();
 
  if (LastCB==Select || LastCB==Fp_order || LastCB==Gel_order) {
     row += 2.0;
     graphText("Starting coordinate: ",6,row);
     offBox = graphTextEntry(offText, 6, 26, row,scanOK);
  }
  return; 
}
